package main

func selectionSort(num []int) {
	length := len(num)
	for i := 0; i < length-1; i++ {
		k := i
		for j := i + 1; j < length; j++ {
			if num[k] > num[j] {
				k = j
			}
		}
		num[i], num[k] = num[k], num[i]
	}
}

func bubbleSort(num []int) {
	length := len(num)
	for i := length - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if num[j] > num[j+1] {
				num[j], num[j+1] = num[j+1], num[j]
			}
		}
	}
}

/* 冒泡排序（标志优化）*/
func bubbleSortWithFlag(nums []int) {
	// 外循环：未排序区间为 [0, i]
	for i := len(nums) - 1; i > 0; i-- {
		flag := false // 初始化标志位
		// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				// 交换 nums[j] 与 nums[j + 1]
				nums[j], nums[j+1] = nums[j+1], nums[j]
				flag = true // 记录交换元素
			}
		}
		if flag == false { // 此轮“冒泡”未交换任何元素，直接跳出
			break
		}
	}
}

func insertSort(num []int) {
	// 5,3,2,4,1
	//1. suppose first number is sorted.
	//2. so unsorted range is 1-4 and sorted range is 0-0
	//3. get a base number,use second number as base.there is 3.
	//4. 3 is lower than 5,so 3 should be moved behind the 5. in this case,array is 3,5 | 2,4,1
	//5. then unsorted range is 2-4 and sorted range is 0-1

	for i := 1; i < len(num); i++ {
		base := num[i]
		j := i - 1
		for j >= 0 && num[j] > base {
			num[j+1] = num[j]
			j--
		}
		num[j+1] = base
	}
}

func partition(num []int, left, right int) int {
	// give 3,5,1,4,2
	// expect 1,2,3,5,4
	// use num[left] as base
	i, j := left, right
	for i < j {
		for i < j && num[j] >= num[left] {
			j--
		}
		for i < j && num[i] <= num[left] {
			i++
		}
		num[i], num[j] = num[j], num[i]
	}
	num[i], num[left] = num[left], num[i]
	return i
}

func quickSort(num []int, left, right int) {
	if left >= right {
		return
	}
	pivot := partition(num, left, right)
	if pivot > 0 {
		quickSort(num, left, pivot-1)
	}
	quickSort(num, pivot+1, right)
}
